{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #十字路口的交通"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: trafficCommand"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #十字路口的交通"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "前往「力扣挑战赛」场馆的道路上，有一个拥堵的十字路口，该十字路口由两条双向两车道的路交叉构成。由于信号灯故障，交警需要手动指挥拥堵车辆。假定路口没有新的来车且一辆车从一个车道驶入另一个车道所需的时间恰好为一秒钟，长度为 4 的一维字符串数组 `directions` 中按照 **东、南、西、北** 顺序记录了四个方向从最靠近路口到最远离路口的车辆计划开往的方向。其中：\n",
    "- `\"E\"` 表示向东行驶；\n",
    "- `\"S\"` 表示向南行驶；\n",
    "- `\"W\"` 表示向西行驶；\n",
    "- `\"N\"` 表示向北行驶。\n",
    "\n",
    "交警每秒钟只能指挥各个车道距离路口最近的一辆车，且每次指挥需要满足如下规则：\n",
    "- 同一秒钟内，一个方向的车道只允许驶出一辆车；\n",
    "- 同一秒钟内，一个方向的车道只允许驶入一辆车；\n",
    "- 同一秒钟内，车辆的行驶路线不可相交。\n",
    "\n",
    "请返回最少需要几秒钟，该十字路口等候的车辆才能全部走完。\n",
    "\n",
    "各个车道驶出的车辆可能的行驶路线如图所示：\n",
    "\n",
    "\n",
    "![图片.png](https://pic.leetcode-cn.com/1630393755-gyPeMM-%E5%9B%BE%E7%89%87.png){:height=\"350px\"}\n",
    "\n",
    "**注意：**\n",
    "- 测试数据保证不会出现掉头行驶指令，即某一方向的行驶车辆计划开往的方向不会是当前车辆所在的车道的方向;\n",
    "- 表示堵塞车辆行驶方向的字符串仅用大写字母 `\"E\"`，`\"N\"`，`\"W\"`，`\"S\"` 表示。\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`directions = [\"W\",\"N\",\"ES\",\"W\"]`\n",
    ">\n",
    ">输出：`2`\n",
    ">\n",
    ">解释：\n",
    ">第 1 秒：东西方向排在最前的车先行，剩余车辆状态 `[\"\",\"N\",\"S\",\"W\"]`；\n",
    ">第 2 秒：南、西、北方向的车行驶，路口无等待车辆；\n",
    ">因此最少需要 2 秒，返回 2。\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`directions = [\"NS\",\"WE\",\"SE\",\"EW\"]`\n",
    ">\n",
    ">输出：`3`\n",
    ">\n",
    ">解释：\n",
    ">第 1 秒：四个方向排在最前的车均可驶出；\n",
    ">第 2 秒：东南方向的车驶出，剩余车辆状态 `[\"\",\"\",\"E\",\"W\"]`；\n",
    ">第 3 秒：西北方向的车驶出。\n",
    "\n",
    "\n",
    "**提示：**\n",
    "- `directions.length = 4`\n",
    "- `0 <= directions[i].length <= 20`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [Y1VbOX](https://leetcode.cn/problems/Y1VbOX/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [Y1VbOX](https://leetcode.cn/problems/Y1VbOX/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"W\",\"N\",\"ES\",\"W\"]', '[\"NS\",\"WE\",\"SE\",\"EW\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "able = set()\r\n",
    "def test(a, b, c, d, A, B, C, D): # eswn\r\n",
    "    if a == C and (b == D or d == A or d == B or c == D):\r\n",
    "        return False\r\n",
    "    if a == B and (b == C or b == D or d == A or c == A):\r\n",
    "        return False\r\n",
    "    return True\r\n",
    "\r\n",
    "for e in ' WNS':\r\n",
    "    for s in ' EWN':\r\n",
    "        for w in ' ESN':\r\n",
    "            for n in ' ESW':\r\n",
    "                eswn = e + s + w + n\r\n",
    "                t = eswn.replace(' ', '')\r\n",
    "                if not t:\r\n",
    "                    continue\r\n",
    "                if len(set(t)) != len(t):\r\n",
    "                    continue\r\n",
    "                if not test(e, s, w, n, *'ESWN'):\r\n",
    "                    continue\r\n",
    "                if not test(s, w, n, e, *'SWNE'):\r\n",
    "                    continue\r\n",
    "                if not test(w, n, e, s, *'WNES'):\r\n",
    "                    continue\r\n",
    "                if not test(n, e, s, w, *'NESW'):\r\n",
    "                    continue\r\n",
    "                able.add(eswn)  \r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def trafficCommand(self, directions: List[str]) -> int:\r\n",
    "        [e, s, w, n] = list(map(len, directions))\r\n",
    "        [ce, cs, cw, cn] = directions\r\n",
    "        f = [[[[100]*(n+1) for _ in range(w+1)] for _ in range(s+1)] for _ in range(e+1)]\r\n",
    "        ddd = {}\r\n",
    "        f[0][0][0][0] = 0\r\n",
    "        for e1 in range(e+1):\r\n",
    "            for s1 in range(s+1):\r\n",
    "                for w1 in range(w+1):\r\n",
    "                    for n1 in range(n+1):\r\n",
    "                        if e1 + s1 + w1 + n1 == 0:\r\n",
    "                            continue\r\n",
    "                        x = 100\r\n",
    "                        for mask in range(1, 16):\r\n",
    "                            v = ce[e1-1] if mask & 1 and e1 else ' '\r\n",
    "                            v += cs[s1-1] if mask & 2 and s1 else ' '\r\n",
    "                            v += cw[w1-1] if mask & 4 and w1 else ' '\r\n",
    "                            v += cn[n1-1] if mask & 8 and n1 else ' '\r\n",
    "                            if v in able:\r\n",
    "                                x = min(x, f[e1-(v[0]!=' ')][s1-(v[1]!=' ')][w1-(v[2]!=' ')][n1-(v[3]!=' ')] + 1)\r\n",
    "                        f[e1][s1][w1][n1] = x\r\n",
    "\r\n",
    "        return f[e][s][w][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "able = set()\n",
    "def test(a, b, c, d, A, B, C, D): # eswn\n",
    "    if a == C and (b == D or d == A or d == B or c == D):\n",
    "        return False\n",
    "    if a == B and (b == C or b == D or d == A or c == A):\n",
    "        return False\n",
    "    return True\n",
    "\n",
    "for e in ' WNS':\n",
    "    for s in ' EWN':\n",
    "        for w in ' ESN':\n",
    "            for n in ' ESW':\n",
    "                eswn = e + s + w + n\n",
    "                t = eswn.replace(' ', '')\n",
    "                if not t:\n",
    "                    continue\n",
    "                if len(set(t)) != len(t):\n",
    "                    continue\n",
    "                if not test(e, s, w, n, *'ESWN'):\n",
    "                    continue\n",
    "                if not test(s, w, n, e, *'SWNE'):\n",
    "                    continue\n",
    "                if not test(w, n, e, s, *'WNES'):\n",
    "                    continue\n",
    "                if not test(n, e, s, w, *'NESW'):\n",
    "                    continue\n",
    "                able.add(eswn)  \n",
    "\n",
    "class Solution:\n",
    "    def trafficCommand(self, directions: List[str]) -> int:\n",
    "        [e, s, w, n] = list(map(len, directions))\n",
    "        [ce, cs, cw, cn] = directions\n",
    "        f = [[[[100]*(n+1) for _ in range(w+1)] for _ in range(s+1)] for _ in range(e+1)]\n",
    "        ddd = {}\n",
    "        f[0][0][0][0] = 0\n",
    "        for e1 in range(e+1):\n",
    "            for s1 in range(s+1):\n",
    "                for w1 in range(w+1):\n",
    "                    for n1 in range(n+1):\n",
    "                        if e1 + s1 + w1 + n1 == 0:\n",
    "                            continue\n",
    "                        x = 100\n",
    "                        for mask in range(1, 16):\n",
    "                            v = ce[e1-1] if mask & 1 and e1 else ' '\n",
    "                            v += cs[s1-1] if mask & 2 and s1 else ' '\n",
    "                            v += cw[w1-1] if mask & 4 and w1 else ' '\n",
    "                            v += cn[n1-1] if mask & 8 and n1 else ' '\n",
    "                            if v in able:\n",
    "                                x = min(x, f[e1-(v[0]!=' ')][s1-(v[1]!=' ')][w1-(v[2]!=' ')][n1-(v[3]!=' ')] + 1)\n",
    "                        f[e1][s1][w1][n1] = x\n",
    "\n",
    "        return f[e][s][w][n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trafficCommand(self, directions: List[str]) -> int:\n",
    "        # max_l = [len(directions[0]), len(directions[1]), len(directions[2]), len(directions[3])]\n",
    "\n",
    "        # f = [[[[None] * (max_l[3] + 1) for _ in range(max_l[2] + 1)] for _ in range(max_l[1] + 1)] for _ in range(max_l[0] + 1)]\n",
    "\n",
    "        # position_maatrix = [[0,  0,  1,  0,  2,  0,  0],\n",
    "        #                  [0,  0,  0,  3,  0,  0,  0],\n",
    "        #                  [4,  0,  5,  0,  6,  0,  7],\n",
    "        #                  [0,  8,  0,  0,  0,  9,  0],\n",
    "        #                  [10, 0, 11,  0,  12, 0, 13],\n",
    "        #                  [0,  0,  0, 14,  0,  0,  0],\n",
    "        #                  [0,  0, 15,  0,  16, 0,  0]]\n",
    "        # start_pos = [[2, 6], [6,4], [4,0],[0,2]]\n",
    "\n",
    "\n",
    "        # dx = [[0, 1, 0, -1], [-1, 0, -1, -1], [0, 1, 0, -1], [1, 1, 1, 0]]\n",
    "        # dy = [[0, -1, -1, -1], [1, 0, -1, 0], [1, 1, 0, 1], [1, 0, -1, 0]]\n",
    "        # d_map = {'E': 0, 'S': 1, 'W': 2, 'N':3}\n",
    "        # candidate_list = []\n",
    "        # for d in range(4):\n",
    "        #     candidate_list.append([])\n",
    "            \n",
    "        #     candidate_list[-1].append([d, []])\n",
    "        #     for target_d in range(4):\n",
    "        #         if d == target_d:\n",
    "        #             continue\n",
    "        #         x = start_pos[d][0] + dx[d][target_d]\n",
    "        #         y = start_pos[d][1] + dy[d][target_d]\n",
    "\n",
    "        #         used_po = []\n",
    "\n",
    "        #         while x >= 0 and x < 7 and y >= 0 and y < 7:\n",
    "        #             if position_maatrix[x][y] > 0:\n",
    "        #                 used_po.append(position_maatrix[x][y])\n",
    "        #                 x += dx[d][target_d]\n",
    "        #                 y += dy[d][target_d]\n",
    "                \n",
    "        #         candidate_list[-1].append([target_d, used_po[:]])\n",
    "        \n",
    "        # valid = set()\n",
    "        # for p0, used0 in candidate_list[0]:\n",
    "        \n",
    "        max_l = [len(directions[0]), len(directions[1]), len(directions[2]), len(directions[3])]\n",
    "\n",
    "        f = [[[[None] * (max_l[3] + 1) for _ in range(max_l[2] + 1)] for _ in range(max_l[1] + 1)] for _ in range(max_l[0] + 1)]\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "                1       2\n",
    "\n",
    "                    3\n",
    "\n",
    "        4       5       6       7\n",
    "\n",
    "            8               9\n",
    "\n",
    "        10      11      12      13\n",
    "\n",
    "                    14\n",
    "\n",
    "                15      16\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        points_matrix = [[0,  0,  1,  0,  2,  0,  0],\n",
    "                         [0,  0,  0,  3,  0,  0,  0],\n",
    "                         [4,  0,  5,  0,  6,  0,  7],\n",
    "                         [0,  8,  0,  0,  0,  9,  0],\n",
    "                         [10, 0, 11,  0,  12, 0, 13],\n",
    "                         [0,  0,  0, 14,  0,  0,  0],\n",
    "                         [0,  0, 15,  0,  16, 0,  0]]\n",
    "\n",
    "        start_coord = [[2, 6], [6, 4], [4, 0], [0, 2]]\n",
    "        #dx和dy表示路线上坐标的变化\n",
    "        #其中dx[0]、dy[0]表示东方的车辆路线，因此只需要考虑原地不动、左下、左、左上三个方向\n",
    "        #另外三个方向的dx和dy也是一样\n",
    "        dx = [[0, 1, 0, -1], [-1, 0, -1, -1], [0, 1, 0, -1], [1, 1, 1, 0]]\n",
    "        dy = [[0, -1, -1, -1], [1, 0, -1, 0], [1, 1, 0, 1], [1, 0, -1, 0]]\n",
    "        d_map = {'E': 0, 'S': 1, 'W': 2, 'N': 3}\n",
    "\n",
    "        candidate_list = []\n",
    "        for d in range(4):\n",
    "            candidate_list.append([])\n",
    "            candidate_list[-1].append([d, []])\n",
    "            for target_d in range(4):\n",
    "                if d == target_d:\n",
    "                    continue\n",
    "                \n",
    "                x = start_coord[d][0] + dx[d][target_d]\n",
    "                y = start_coord[d][1] + dy[d][target_d]\n",
    "                used_points = []\n",
    "                #将当前行进路线上经过的交叉点加入到used_points中\n",
    "                while x >= 0 and x < 7 and y >= 0 and y < 7:\n",
    "                    if points_matrix[x][y] > 0:\n",
    "                        used_points.append(points_matrix[x][y])\n",
    "                    x += dx[d][target_d]\n",
    "                    y += dy[d][target_d]\n",
    "                \n",
    "                #candidate_list储存的是当前方向上，目的地为target_d时需要经过的交叉点集合used_points\n",
    "                candidate_list[-1].append([target_d, used_points[:]])\n",
    "\n",
    "        #valid储存合法的行车方案\n",
    "        valid = set()\n",
    "\n",
    "        #枚举四个方向上行车方案的组合\n",
    "        for p0, used0 in candidate_list[0]:\n",
    "            for p1, used1 in candidate_list[1]:\n",
    "                for p2, used2 in candidate_list[2]:\n",
    "                    for p3, used3 in candidate_list[3]:\n",
    "                        #cnt记录经过交叉点的次数\n",
    "                        cnt = {}\n",
    "                        for p in used0:\n",
    "                            cnt[p] = cnt.get(p, 0) + 1\n",
    "                        for p in used1:\n",
    "                            cnt[p] = cnt.get(p, 0) + 1\n",
    "                        for p in used2:\n",
    "                            cnt[p] = cnt.get(p, 0) + 1\n",
    "                        for p in used3:\n",
    "                            cnt[p] = cnt.get(p, 0) + 1\n",
    "\n",
    "                        #cnt为空表示所有方向的车辆都在原地停留，这也是不合法的行动方案\n",
    "                        if not cnt or max(cnt.values()) != 1:\n",
    "                            continue\n",
    "                        \n",
    "                        valid.add((p0, p1, p2, p3))\n",
    "        #记忆化搜索实现\n",
    "        def dfs(pos, f):\n",
    "            if f[pos[0]][pos[1]][pos[2]][pos[3]] is not None:\n",
    "                return f[pos[0]][pos[1]][pos[2]][pos[3]]\n",
    "            \n",
    "            if pos == max_l:\n",
    "                return 0\n",
    "            \n",
    "            candidate_list = []\n",
    "            for d in range(4):\n",
    "                candidate_list.append([])\n",
    "                candidate_list[-1].append([pos[d], d])\n",
    "                if pos[d] < max_l[d]:\n",
    "                    target_d = d_map[directions[d][pos[d]]]\n",
    "                    candidate_list[-1].append([pos[d] + 1, target_d])\n",
    "            \n",
    "            f[pos[0]][pos[1]][pos[2]][pos[3]] = sum(max_l) + 1\n",
    "            for p0, d0 in candidate_list[0]:\n",
    "                for p1, d1 in candidate_list[1]:\n",
    "                    for p2, d2 in candidate_list[2]:\n",
    "                        for p3, d3 in candidate_list[3]:\n",
    "                            if (d0, d1, d2, d3) in valid:\n",
    "                                f[pos[0]][pos[1]][pos[2]][pos[3]] = min(f[pos[0]][pos[1]][pos[2]][pos[3]], dfs([p0, p1, p2, p3], f) + 1)\n",
    "            \n",
    "            return f[pos[0]][pos[1]][pos[2]][pos[3]]\n",
    "        \n",
    "        return dfs([0, 0, 0, 0], f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef trafficCommand(self, directions):\n",
    "\t\tmap0 = [{'N': 66, 'W': 120, 'S': 26944}, {'N': 34850, 'W': 42120, 'E': 36864}, \\\n",
    "\t\t\t  {'N': 662, 'S': 16896, 'E': 7680}, {'W': 9, 'S': 17425, 'E': 4389}]\n",
    "\t\tq = deque([[0,0,0,0,0]])\n",
    "\t\tvisited = {(0,0,0,0)}\n",
    "\t\tt = sum([len(s) for s in directions])\n",
    "\t\tif t == 0:\n",
    "\t\t\treturn 0\n",
    "\t\twhile True:\n",
    "\t\t\tstep, e, s, w, n = q.popleft()\n",
    "\t\t\tids = [e, s, w, n]\n",
    "\t\t\tpool = set()\n",
    "\t\t\tfor md in range(15, 0, -1):\n",
    "\t\t\t\tmark = 0\n",
    "\t\t\t\tvalid = True\n",
    "\t\t\t\tnid = [e, s, w, n]\n",
    "\t\t\t\tfor i in range(4):\n",
    "\t\t\t\t\tif md >> i & 1 == 1 and ids[i] < len(directions[i]):\n",
    "\t\t\t\t\t\tcur = map0[i][directions[i][ids[i]]]\n",
    "\t\t\t\t\t\tif cur & mark != 0:\n",
    "\t\t\t\t\t\t\tvalid = False\n",
    "\t\t\t\t\t\t\tbreak\n",
    "\t\t\t\t\t\tnid[i] += 1\n",
    "\t\t\t\t\t\tmark |= cur\n",
    "\t\t\t\tif valid:\n",
    "\t\t\t\t\tfor x in pool:\n",
    "\t\t\t\t\t\tif x & md == md:\n",
    "\t\t\t\t\t\t\tvalid = False\n",
    "\t\t\t\t\t\t\tbreak\n",
    "\t\t\t\tif valid:\n",
    "\t\t\t\t\tpool.add(md)\n",
    "\t\t\t\t\tif tuple(nid) not in visited:\n",
    "\t\t\t\t\t\tif sum(nid) == t:\n",
    "\t\t\t\t\t\t\treturn step + 1\n",
    "\t\t\t\t\t\tvisited.add(tuple(nid))\n",
    "\t\t\t\t\t\tq.append([step + 1] + nid)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
